package com.rui.study.algorithm.P_动态规划_最大公共子串;

import java.util.Random;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2019-01-04 16:06
 **/
public class Solution1动态规划_状态转移表法 {

    public int lcs(char[] a, char[] b) {
        int m = a.length, n = b.length;
        Integer[][] maxlcs = new Integer[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {

                if (i == 0 && j == 0) {
                    if (a[i] == b[j]) maxlcs[i][j] = 1;
                    else maxlcs[i][j] = 0;
                    continue;
                }

                if (i == 0) {
                    if (a[i] == b[j]) maxlcs[i][j] = 1;
                    else maxlcs[i][j] = maxlcs[i][j-1];
                    continue;
                }

                if (j == 0) {
                    if (a[i] == b[j]) maxlcs[i][j] = 1;
                    else maxlcs[i][j] = maxlcs[i-1][j];
                    continue;
                }

                if (a[i] == b[j]) {
                    maxlcs[i][j] = max(maxlcs[i-1][j-1] + 1, maxlcs[i-1][j], maxlcs[i][j-1]);
                } else {
                    maxlcs[i][j] = max(maxlcs[i-1][j-1], maxlcs[i-1][j], maxlcs[i][j-1]);
                }
            }
        }
        return maxlcs[m-1][n-1];
    }
    
    private int max(int x, int y, int z) {
        int max = Integer.MIN_VALUE;
        if (x > max) max = x;
        if (y > max) max = y;
        if (z > max) max = z;
        return max;
    }


    public static void main(String[] args) {
//        char[] a = "mtacnu".toCharArray();
//        char[] b = "mitcmu".toCharArray();
        int len = 500, ratio = 4;
        char[] a = new char[len];
        char[] b = new char[len];
        Random r1 = new Random(31);
        Random r2 = new Random(31);
        Random r3 = new Random(7);
        StringBuffer bbuf = new StringBuffer();
        for (int i = 0; i < len; i++) {
            a[i] = (char) (97 + r1.nextInt(26));
            char bc = (char) (97 + r2.nextInt(26));
            if (i % ratio != 0) {
                bbuf.append(bc);
            } else {
                bbuf.append((char) (97 + r3.nextInt(26)));
            }
        }
        b = bbuf.toString().toCharArray();
        System.out.println("a: " + String.valueOf(a));
        System.out.println("b: " + String.valueOf(b));
        Solution1动态规划_状态转移表法 solution = new Solution1动态规划_状态转移表法();
        long start = System.currentTimeMillis();
        int maxlcs = solution.lcs(a, b);
        long end = System.currentTimeMillis();
        System.out.println("最大公共子串长度：" + maxlcs + ", 用时：[" + (end - start) + "ms]");
    }
    
}
